package dp

// https://leetcode-cn.com/problems/jump-game/
// 是否可跳跃到一个节点
// 算法: 动态规划
// 时间复杂度: O(n)
// can[n] = can[n-1] & maxremainstep[n-1] >= 1, maxremainstep[n] = max(maxremainstep[n-1] - 1, jump[n])
func CanJump(nums []int) bool {
	if len(nums) == 0 {
		return false
	}

	canArr := make([]bool, len(nums))
	maxRemainStep := make([]int, len(nums))

	canArr[0] = true
	maxRemainStep[0] = nums[0]

	for index := 1; index < len(nums); index++ {
		canArr[index] = canArr[index-1] && maxRemainStep[index-1] >= 1
		maxRemainStep[index] = maxInt(maxRemainStep[index-1]-1, nums[index])
	}

	return canArr[len(nums)-1]
}

// func maxInt(a, b int) int {
// 	if a > b {
// 		return a
// 	}
// 	return b
// }
